//给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 
//
// 叶子节点 是指没有子节点的节点。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
//输出：[[5,4,11,2],[5,8,4,5]]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：root = [1,2,3], targetSum = 5
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：root = [1,2], targetSum = 0
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点总数在范围 [0, 5000] 内 
// -1000 <= Node.val <= 1000 
// -1000 <= targetSum <= 1000 
// 
//
// 注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/ 
//
// 
//
// Related Topics 树 深度优先搜索 回溯 二叉树 👍 468 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-05-09 00:10:32
 * @description LCR 153.二叉树中和为目标值的路径
 */
public class ErChaShuZhongHeWeiMouYiZhiDeLuJingLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ErChaShuZhongHeWeiMouYiZhiDeLuJingLcof fun=new ErChaShuZhongHeWeiMouYiZhiDeLuJingLcof();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

//  Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
		 /*
		 * the target is the sum of the path from the root node to the leaf node,
		 * so we can use the depth-first search method to traverse the tree,
		 * and when we reach the leaf node, we can check whether the sum of the path is equal to the target.
		 * */
    public List<List<Integer>> pathTarget(TreeNode root, int target) {
		List<List<Integer>> result=new ArrayList<>();
		if(root==null){
			return result;
		}
		dfs(root,target,0,new ArrayList<>(),result);
		return result;
    }
	private void dfs(TreeNode root, int target,int currentSum, List<Integer> path, List<List<Integer>> result) {
		currentSum+=root.val;
		path.add(root.val);
		if(root.left==null&&root.right==null){
			if(currentSum==target){
				result.add(new ArrayList<>(path));
			}
			return;
		}
		if(root.left!=null){
			dfs(root.left,target,currentSum,path,result);
			path.remove(path.size()-1);
		}

		if(root.right!=null){
			dfs(root.right,target,currentSum,path,result);
			path.remove(path.size()-1);
		}
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
